package Midium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

// 846.一手顺子
/*
 * 例：hand = [1,2,3,6,2,3,4,7,8], W = 3
 * true --> [1,2,3]，[2,3,4]，[6,7,8]
 * 思：
 * 先排序
 * [1,2,3,6,2,3,4,7,8] --> [1,2,2,3,3,4,6,7,8]
 * 每次先挑一个最小的数，然后顺着找，找不到连续的W-1个数，就直接返回false
 * 如果找到了W个连续的数，则再找下一组
 *
 * 特别注意：[1,2,3,4,5,6] W=2 时，应该返回true
 * */
public class Solution846 {
    public static boolean isNStraightHand(int[] hand, int W) {
        if (hand.length % W != 0)
            return false;
        if (W == 1)
            return true;
        Arrays.sort(hand);
        int count = 0;
        while (count < hand.length) {
            // 每次取出第一个不为-1的数
            int j = 0;
            while (hand[j] == -1 && j < hand.length) {
                j++;
            }
            int temp = hand[j]; //取出当前最小数
            hand[j++] = -1;
            count++;
            // 开始寻找比它大的W-1个连续的数
            for (int k = 1; k < W; k++) {
                while (j < hand.length) {
                    if (hand[j] == temp || hand[j] == -1)
                        j++;
                    else break;
                }
                if (j < hand.length && hand[j] == temp + 1) {
                    temp = hand[j];
                    hand[j] = -1;
                    count++;
                    j++;
                } else {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
//        isNStraightHand(new int[]{1,2,3,6,2,3,4,7,8},3);
//        isNStraightHand(new int[]{1}, 1);
        boolean nStraightHand = isNStraightHand(new int[]{2, 1}, 2);
        System.out.println(nStraightHand);
    }
}
